//给你一个字符串 s，找到 s 中最长的 回文 子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母组成 
// 
//
// Related Topics 双指针 字符串 动态规划 👍 7541 👎 0

package leetcode.editor.cn;

/**
 * @author Leunghan
 * @date 2025-02-26 21:17:03
 */
class LongestPalindromicSubstring {
    public static void main(String[] args) {
        Solution solution = new LongestPalindromicSubstring().new Solution();
        solution.longestPalindrome("cbbd");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String longestPalindrome(String s) {
            if (s.length() <= 1) {
                return s;
            }
            boolean[][] dp = new boolean[s.length()][s.length()];
            int begin = 0, end = 0, len = s.length();
            char[] charArray = s.toCharArray();
            for (int i = 0; i < len; i++) {
                dp[i][i] = true;
                if (i < len - 1) {
                    dp[i][i + 1] = charArray[i] == charArray[i + 1];
                    if (dp[i][i + 1] && end - begin < 1) {
                        begin = i;
                        end = i + 1;
                    }
                }
            }

            for (int subL = 3; subL <= len; subL++) {
                for (int i = 0; i < s.length(); i++) {
                    int j = i + subL - 1;
                    if (j >= len) {
                        break;
                    }
                    dp[i][j] = dp[i + 1][j - 1] && charArray[i] == charArray[j];
                    if (dp[i][j] && j - i > end - begin) {
                        begin = i;
                        end = j;
                    }
                }
            }
            return s.substring(begin, end + 1);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}